package week_07;

import java.util.HashMap;

public class Trie_208 {
    /**
     * Initialize your data structure here.
     */
    TrieNode node;

    public Trie_208() {
         node = new TrieNode();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        char[] chars = word.toCharArray();
        TrieNode p = this.node;
        for (char c : chars) {
            if (!p.map.containsKey(c)) {
                p.map.put(c, new TrieNode());
            }
            p = p.map.get(c);
        }
        p.count += 1;
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        char[] chars = word.toCharArray();
        TrieNode p = this.node;
        for (char c : chars) {
            if (!p.map.containsKey(c)) return false;
            p = p.map.get(c);
        }
        return p.count > 0;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        char[] chars = prefix.toCharArray();
        TrieNode p = this.node;
        for (char c : chars) {
            if (!p.map.containsKey(c)) return false;
            p = p.map.get(c);
        }
        return true;
    }

    public class TrieNode {
        int count;
        HashMap<Character, TrieNode> map;

        TrieNode() {
            this.count = 0;
            this.map = new HashMap<>();
        }
    }

    public static void main(String[] args) {
        Trie_208 obj = new Trie_208();
        String word = "instantiated";
        obj.insert(word);
        boolean param_2 = obj.search(word);
        boolean param_3 = obj.startsWith(word);
        System.out.println(param_2);
        System.out.println(param_3);
    }
}
